package LeetCode_236;

import LeetCode_206.ListNode;

import java.util.List;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/30 10:27
 * 236. 二叉树的最近公共祖先
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    private boolean containsNode(TreeNode root, TreeNode target) {
        if (root == null) {
            return false;
        }
        if (root == target) {
            return true;
        }
        return containsNode(root.left, target)
                || containsNode(root.right, target);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //这里没有判断过 root == null 的情况
        //p,q都在子树中，则root最少有一个值
        //当root.left == null|| root.right == null 就不会递归，所以无需考虑
        if (root == p || root == q) {
            return root;
        }
        // 判断情况

        boolean pInLeft = containsNode(root.left, p); // p 在不在左子树中
        boolean qInLeft = containsNode(root.left, q);// q 在不在左子树中
        // 隐含前提：p 和 q 一定是树中的结点         且 q,p不是一个节点
        // p、q 只有三种可能：要么是根（这个我们排除了）
        // 只有左子树和右子树两种情况
        // 所以，如果不在左子树，一定在右子树
        // 所以没必要再去找右子树了
        if (pInLeft == true && qInLeft == true){
            // 说明 p、q 都在左子树
            return lowestCommonAncestor(root.left,p,q);
        }
        if (pInLeft == false && qInLeft == false){
            // 说明 p、q 都在右子树
            return lowestCommonAncestor(root.right,p,q);
        }
        // 说明一个左，一个右，谁左谁右不关心了
        return root;
    }
}
